#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""

# https://www.jianshu.com/p/5045dda5ea1f



class Solution:
    """
    @param nums: A list of integers
    @param k: An integer denote to find k non-overlapping subarrays
    @return: An integer denote the sum of max k non-overlapping subarrays
    """
    def maxSubArray(self, nums, k):
        self.nums = nums
        self.n = len(nums)
        self.k = k
        self.init_data()
        self.solve()
        return self.global_max[self.k][self.n-1]

    def init_data(self):
        self.local_max = self.make_matrix(self.k+1, self.n)
        self.global_max = self.make_matrix(self.k+1, self.n)

    def make_matrix(self, m, n, init_value=0):
        # l = [0] * n
        l = [init_value] * n
        m = [list(l) for i in range(m)]
        return m

    def solve(self):
        for split_n in range(1, self.k+1):
            # 从1次分割到k次分割
            self.calc_local_global(split_n)

    def calc_local_global(self, split_n):
        start = split_n - 1
        self.local_max[split_n][start] = self.global_max[split_n][start] = sum(self.nums[0:start+1])

        for col in range(start+1, self.n):
            # if col == start:
            #     self.local_max[split_n][col] = self.global_max[split_n][col] = sum(self.nums[0:split_n])
            # else:
            n = self.nums[col]
            local_v1 = self.local_max[split_n][col-1] + n
            local_v2 = self.global_max[split_n-1][col-1] + n

            self.local_max[split_n][col] = max(local_v1, local_v2)
            local_max = max(local_v1, local_v2)
            self.local_max[split_n][col] = local_max
            self.global_max[split_n][col] = max(local_max, self.global_max[split_n][col-1])


def main():
    s = Solution()
    # s.maxSubArray([-1,4,-2,3,-2,3], 2)
    ret = s.maxSubArray([1, 3, -1, 1, 3], 2)

    print(s.local_max)
    print(s.global_max)
    print(ret)

if __name__ == "__main__":
    main()
